public class TravelingSalesmanProblem {
    /**
     * 旅行售货员问题：描述的是给定一组城市和每对城市之间的举例，求解一条最短路径，使得该路径经过每个城市1次并最后返回起始位置城市
     *
     */
    private int[][] distanceMatrix; //有关城市距离的矩阵
    private int[] bestPath; //最佳路径
    private int bestDistance; //最短距离

    public TravelingSalesmanProblem(int[][] distanceMatrix) {
        this.distanceMatrix = distanceMatrix;
        this.bestPath = new int[distanceMatrix.length];
        this.bestDistance = Integer.MAX_VALUE;
    }

    public int[] getBestPath() {
        return bestPath;
    }

    public int getBestDistance() {
        return bestDistance;
    }

    public void solve(){
        // 用于存储当前已经选择的路径
        int[] path=new int[distanceMatrix.length];
        // 用于记录城市是否已经访问
        boolean[] visited = new boolean[distanceMatrix.length];
        // 从城市0开始
        path[0]=0;
        visited[0]=true;

        backtrack(path, visited, 1, 0); // 调用回溯算法求解
    }

    public void backtrack(int[] path,boolean[] visited,int level,int distance){
        if(level== path.length){
            // 所有的城市都选过了
            if(distance+distanceMatrix[path[level-1]][0]<bestDistance){
                // 如果当前路径更短，更新最优解
                System.arraycopy(path, 0, bestPath, 0, path.length);
                bestDistance = distance + distanceMatrix[path[level - 1]][0];
            }
            return;
        }

        for(int i=1;i<path.length;i++){
            // 遍历剩余的为访问的城市
            if(!visited[i]){
                path[level]=i; //将第i个未访问的城市添加到路径中去
                visited[i]=true;
                backtrack(path, visited, level + 1, distance + distanceMatrix[path[level - 1]][i]); // 递归继续选择下一个城市
                visited[i] = false; // 回溯，将第i个城市标记为未访问
            }
        }
    }

    public static void main(String[] args) {
        int[][] distanceMatrix = {
                {0, 10, 15, 20},
                {10, 0, 35, 25},
                {15, 35, 0, 30},
                {20, 25, 30, 0}
        };

        TravelingSalesmanProblem tsp = new TravelingSalesmanProblem(distanceMatrix);
        tsp.solve();
        int[] bestPath = tsp.getBestPath();
        int bestDistance = tsp.getBestDistance();

        System.out.print("Best Path: ");
        for (int i : bestPath) {
            System.out.print(i + " ");
        }
        System.out.println("\nBest Distance: " + bestDistance);
    }

}
